package hot100.logos41To50;

import hot100.datastruct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author logos
 * date 2025/7/14 11:45
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos41 {

    /**
     * 41. 二叉树的层序遍历
     * https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution1 {
        public static final int MAX_N = 2001;

        public static TreeNode que[] = new TreeNode[MAX_N];

        public static int l, r;

        public List<List<Integer>> levelOrder(TreeNode root) {
            l = r = 0;
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            que[r++] = root;
            while (l < r) {
                int k = r - l;
                List<Integer> tmp = new ArrayList<>();
                for (int i = 0; i < k; i++) {
                    TreeNode cur = que[l++];
                    tmp.add(cur.val);
                    if (cur.left != null) {
                        que[r++] = cur.left;
                    }
                    if (cur.right != null) {
                        que[r++] = cur.right;
                    }
                }
                ans.add(tmp);
            }
            return ans;
        }
    }

    class Solution2 {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            dfs(root, 0, ans);
            return ans;
        }

        public void dfs(TreeNode root, int level, List<List<Integer>> ans) {
            if (root == null) {
                return;
            }
            if (level == ans.size()) {
                ans.add(new ArrayList<>());
            }
            ans.get(level).add(root.val);
            dfs(root.left, level + 1, ans);
            dfs(root.right, level + 1, ans);
        }
    }
}
